import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

//{10,6,14,4,8,12,16}
public class Test {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && Math.abs(i - map.get(nums[i])) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }

    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
        }
        return false;
    }

    public static int numJewelsInStones(String jewels, String stones) {
        Set<Character> stone = new HashSet<>();
        Set<Character> jewel = new HashSet<>();
        for (char ch : jewels.toCharArray()) {
            jewel.add(ch);
        }
        for (char ch : stones.toCharArray()) {
            stone.add(ch);
        }
        int countJewels = 0;
        for (char ch : stone) {
            if (jewel.contains(ch)) {
                countJewels++;
            }
        }
        return countJewels;
    }

    public static void main4(String[] args) {
        String jewels = "z";
        String stones = "ZZ";
        numJewelsInStones(jewels, stones);
    }

    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                int val = map.get(num);
                map.put(num, val + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (int num : nums) {
            if (map.get(num) == 1) {
                return num;
            }
        }
        return -1;
    }

    public static void main3(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(2);
        root.left.left.left.left = new TreeNode(1);
        root = convert(root);
        linkedPrint(root);
    }

    static List<TreeNode> list = new ArrayList<>();

    public static TreeNode convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        inorder(pRootOfTree);
        TreeNode head = list.get(0);
        TreeNode cur = head;
        TreeNode prev = null;
        for (int i = 1; i < list.size(); i++) {
            TreeNode curNext = list.get(i);
            cur.left = curNext;
            if (i > 1) {
                cur.right = prev;
            }
            prev = cur;
            cur = curNext;
        }
        cur.right = prev;
        cur.left = null;
        return head;
    }

    public static void linkedPrint(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.left;
        }
    }

    private static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root);
        inorder(root.right);
    }


    //创建升序数组
    public static void createArray1(int[] arr) {
        for (int i = 1; i < 10000; i++) {
            arr[i - 1] = i;
        }
    }

    //创建逆序数组
    public static void createArray2(int[] arr) {
        for (int i = 0; i < 10000; i++) {
            arr[i] = 10000 - i;
        }
    }

    public static void main1(String[] args) {
        int[] a = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        Sort.quickSort2(a);
        for (int x : a) {
            System.out.print(x + " ");
        }
    }

//    public static void main(String[] args) {
//        int[] a = {10,9,8,7,6,5,4,3,2,1};
//        Sort.radixSort(a);
//        for (int x : a) {
//            System.out.print(x + " ");
//        }
//    }

//    public static void main(String[] args) {
//        int[] a = {5,4,3,2,1};
//        Sort.heapSort(a, a.length);
//        for (int x : a) {
//            System.out.print(x + " ");
//        }
//    }

//    public static void main(String[] args) {
//        int[] arr = {5,2,1,3,4};
//        Sort.selectSortOP(arr);
//        for (int x : arr) {
//            System.out.print(x + " ");
//        }

//        int[] arr2 = new int[10000];
//        Test.createArray2(arr2);
//        long s2 = System.currentTimeMillis();
//        Sort.insertSort(arr2);
//        long e2 = System.currentTimeMillis();
//        System.out.println("直接插入排序的数组逆序的情况："+(e2 - s2));
//
//        int[] arr1 = new int[10000];
//        Test.createArray2(arr1);
//        long s1 = System.currentTimeMillis();
//        Sort.shellSort(arr2);
//        long e1 = System.currentTimeMillis();
//        System.out.println("希尔排序的数组逆序的情况："+(e1 - s1));


//        int[] arr1 = new int[10000];
//        Test.createArray1(arr1);
//        long s1 = System.currentTimeMillis();
//        Sort.insertSort(arr1);
//        long e1 = System.currentTimeMillis();
//        System.out.println("数组有序的情况："+(e1 - s1));
//
//        int[] arr2 = new int[10000];
//        Test.createArray2(arr2);
//        long s2 = System.currentTimeMillis();
//        Sort.insertSort(arr2);
//        long e2 = System.currentTimeMillis();
//        System.out.println("数组逆序的情况："+(e2 - s2));
//    }

    //        Queue<Student> m = new PriorityQueue<Student>(new Comparator<Student>() {
//            @Override
//            public int compare(Student o1, Student o2) {
//                return o1.age - o2.age;
//            }
//        });
//        Student lisi = new Student(12, "lisi");
//        Student zhangsan = new Student(13, "zhangsan");
//        m.offer(lisi);
//        m.offer(zhangsan);
//        System.out.println(m.poll());
//        System.out.println(m.poll());
//    public static void main(String[] args) {
//        Queue<Integer> m = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2 - o1;
//            }
//        });
//        m.offer(10);
//        m.offer(1000);
//        System.out.println(m.poll());
//        System.out.println(m.poll());
//    }

    public static int[] maxK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(k);
        //1.遍历数组的前k个放到堆当中。时间复杂度：K*logK
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //2.遍历剩下的k-1个，每次和堆顶元素进行比较
        //堆顶元素小的时候，就出堆。时间复杂度：(N-k)*logk
        for (int i = k; i < arr.length; i++) {
            int val = minHeap.peek();
            if (val < arr[i]) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        //3.将堆内的三个元素依次交给ret数组
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

//    public static void main(String[] args) {
//        new PriorityQueue<>();
//    }
//    public static void main(String[] args) {
//        TestHeap testHeap = new TestHeap();
//        int[] array = {27,15,19,18,28,34,65,49,25,37};
//        testHeap.initElem(array);
//        testHeap.createHeap();
//        for (int i = 0; i < testHeap.elem.length; i++) {
//            System.out.print(testHeap.elem[i] + " ");
//        }
//    }
}
